// Problem: H - Span
// Idea: Sweep using a stack - similar to the famous problem
//       "Largest Rectangle in a Histogram" (Ulm 2003).
// Language: C++
// Author: Ivan Vladimirov Ivanov (ivan.vladimirov.ivanov@gmail.com)

#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

#define MAX   1500005
#define MAX_N 100005

void init(void);

void input(void);
void solve(void);

char sieve[MAX];
vector <int> primes;

int n, m;
int A[MAX_N];
int S[MAX_N];
int L[MAX_N];
int SP[MAX_N];

int main(void)
{
  init();

  int t;
  scanf("%d", &t);
  while(t--) {
    input();
    solve();
  }

  return 0;
}

void init(void)
{
  primes.clear();
  memset(sieve, 1, sizeof(sieve));

  for(int i = 2; i * i < MAX; i++) {
    if(!sieve[i]) continue;
    for(int j = i + i; j < MAX; j += i) sieve[j] = 0;
  }

  for(int i = 2; i < MAX; i++) {
    if(sieve[i]) primes.push_back(i);
  }
}

void input(void)
{
  scanf("%d %d", &n, &m);
  for(int i = 0; i < n; i++) A[i] = primes[i] % m;
}

void solve(void)
{
  int t = 0;
  for(int i = 0; i < n; i++) {
    L[i] = i;
    while(t > 0 && A[i] >= A[S[t - 1]]) L[i] = L[S[--t]];
    SP[i] = i - L[i] + 1;
    S[t++] = i;
  }

  int res = 0;
  for(int i = 0; i < n; i++) res = (res + SP[i]) % m;

  printf("%d\n", res);
}

